//给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。 
//
// 
//
// 注意： 
//
// 
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹−1]。本题中，如果除法结果溢出，则返回 231 − 1 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：a = 15, b = 2
//输出：7
//解释：15/2 = truncate(7.5) = 7
// 
//
// 示例 2： 
//
// 
//输入：a = 7, b = -3
//输出：-2
//解释：7/-3 = truncate(-2.33333..) = -2 
//
// 示例 3： 
//
// 
//输入：a = 0, b = 1
//输出：0 
//
// 示例 4： 
//
// 
//输入：a = 1, b = 1
//输出：1 
//
// 
//
// 提示: 
//
// 
// -2³¹ <= a, b <= 2³¹ - 1 
// b != 0 
// 
//
// 
//
// 注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/ 
//
// 
//
// Related Topics 数学 👍 293 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-01-06 11:44:20
 * @description LCR 001.两数相除
 
 */
 
public class Xoh6Oh {
    public static void main(String[] args) {
    //测试代码
    Xoh6Oh fun = new Xoh6Oh();
    Solution solution= fun.new Solution();
        System.out.println(solution.divide(-2147483648,-1));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //超时
    public int divide1(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }
        if (a == Integer.MIN_VALUE && b == 1) {
            return Integer.MIN_VALUE;
        }
        int t=0;
        int i=0;
        boolean flag=a<0^b<0;
        a=Math.abs(a);
        b=Math.abs(b);
        for (; i <=a; i++) {
            if(t+b>a) return flag?-i:i;
            if(t+b==a) return flag?-(i+1):i+1;
            t+=b;
        }
        return flag?-i:i;
    }
    //二分，因为只有32位置整数，下界1，上界2^31 -1
    //同时 计算加法时，可能溢出， 因此判断条件改为减法，
    public int divide2(int a, int b) {
        if (a == Integer.MIN_VALUE) {
            if (b == 1) {
                return Integer.MIN_VALUE;
            } if (b == -1) {
                return Integer.MAX_VALUE;
            }
        }
        if (b == Integer.MIN_VALUE) {
            return a == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (a == 0) {
            return 0;
        }
        //把所有正数取反，就可以统一处理
        boolean rev=false;
        if(a>0){
            a=-a;
            rev=!rev;
        }
        if(b>0){
            b=-b;
            rev=!rev;
        }
        int l=1,r=Integer.MAX_VALUE,res=0;
        while (l<=r){
            int m=l+((r-l)>>1);
            boolean check=fastMulti(a,m,b);
            if(check){
                res=m;
                if(m==Integer.MAX_VALUE){
                    break;
                }
                l=m+1;
            }else{
                r=m-1;
            }
        }
        return rev?-res:res;
    }
    //不能使用乘法，所以使用类似快速幂的快速乘
    //函数的目标是判断 b * m >= a 是否成立。false就是不成立
    public boolean fastMulti(int a,int m,int b){
        //a,b是负数，m是正数，判断b*m>=a是否成立
        int res=0;
        while (m!=0){
            if((m&1)==1){
                if(res<a-b){
                    return false;
                }
                res=res+b;
            }
            if(m!=1){
                if(b<a-b){
                    return false;
                }
                b+=b;
            }
            m>>=1;
        }
        return true;
    }
        // 慢开始，倍增，拥塞避免
        public int divide(int a, int b) {
            // 溢出的情况
            if (a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
            if (a == Integer.MIN_VALUE && b == 1) return Integer.MIN_VALUE;

            // 商的符号位
            boolean sign = (a > 0 && b > 0) || (a < 0 && b < 0);

            // 都转成负数好了，因为 -2^31 转成正数会越界
            if (a > 0) a = -a;
            if (b > 0) b = -b;

            int div = 0;
            //因为都是负数，所以一开始b负的比a少，就比a大
            while (a <= b) { // abs(a) > abs(b)
                int b_ = b, count = 1;
                //b成倍数增加
                while (b_ >= Integer.MIN_VALUE >> 1 && a <= b_ + b_) {
                    b_ += b_;
                    count += count;
                }
                //当不走内部循环的时候，外部b又从一倍开始
                a -= b_;
                div += count;
            }

            return sign ? div : -div;
        }


}
//leetcode submit region end(Prohibit modification and deletion)

}
